package com.tachoknight.geocaching.tsp;

import java.util.ArrayList;
import java.util.List;

import com.tachoknight.geocaching.Waypoint;

public class NaiveFrog
{
	/* What is passed to us */
	private Waypoint startingPoint;
	private List<Waypoint> waypoints;

	/* Working variables */
	private List<Waypoint> nwList = new ArrayList<Waypoint>();
	private List<Waypoint> neList = new ArrayList<Waypoint>();
	private List<Waypoint> swList = new ArrayList<Waypoint>();
	private List<Waypoint> seList = new ArrayList<Waypoint>();

	/* Our final list */
	private List<Waypoint> optimizedWaypoints = new ArrayList<Waypoint>();

	public NaiveFrog(Waypoint startingPoint, List<Waypoint> waypoints)
	{
		this.startingPoint = startingPoint;
		this.waypoints = waypoints;

		/*
		 * First point in the optimized list is the starting point (so we only
		 * have to return the single list)
		 */
		this.optimizedWaypoints.add(startingPoint);

		createTour();
	}

	/*
	 * Assume the first waypoint in the list is the starting point
	 */
	public NaiveFrog(List<Waypoint> waypoints)
	{
		this.startingPoint = waypoints.get(0);
		this.waypoints = waypoints;
		this.waypoints.remove(0);

		/*
		 * First point in the optimized list is the starting point (so we only
		 * have to return the single list)
		 */
		this.optimizedWaypoints.add(startingPoint);

		createTour();
	}

	private void createTour()
	{
		fillCompassLists();

		/*
		 * Now run nearest-neighbor on each of the lists, where we use our
		 * starting point (this.startingPoint) as the starting point for the NW
		 * list, then we use the last item of each of the previous lists to
		 * chain them together. If a list doesn't have any elements, we revert
		 * to our original starting point.
		 */
		NearestNeighbor nwNN = new NearestNeighbor(startingPoint, nwList);
		NearestNeighbor neNN = new NearestNeighbor(	nwList.size() == 0	? startingPoint
																		: nwList.get(nwList.size() - 1),
													neList);
		NearestNeighbor swNN = new NearestNeighbor(	neList.size() == 0	? startingPoint
																		: neList.get(neList.size() - 1),
													swList);
		NearestNeighbor seNN = new NearestNeighbor(	swList.size() == 0	? startingPoint
																		: swList.get(swList.size() - 1),
													seList);

		/* And add all the lists together... */
		this.optimizedWaypoints.addAll(nwNN.getSortedWaypoints());
		this.optimizedWaypoints.addAll(neNN.getSortedWaypoints());
		this.optimizedWaypoints.addAll(swNN.getSortedWaypoints());
		this.optimizedWaypoints.addAll(seNN.getSortedWaypoints());
	}

	/*
	 * The starting point is in the center of four squares, labeled NW, NE, SW,
	 * SE. All the waypoints must fall into one of those squares, based on where
	 * each point is from the center, starting point (this.startingPoint).
	 * 
	 * Note: This assumes you're not standing on the equator or at the prime
	 * meridian
	 */
	private void fillCompassLists()
	{
		for (Waypoint wp : waypoints)
		{
			/*
			 * If this latitude is less than the starting point (higher) and the
			 * longitude is greater than the starting point (to the left), put
			 * it in the NW list.
			 */
			if (wp.getLatitude() > startingPoint.getLatitude() && wp.getLongitude() < startingPoint.getLongitude())
			{
				nwList.add(wp);
			}
			/*
			 * If this latitude is less than the starting point (higher) and the
			 * longitude is less than the starting point (to the right), put it
			 * in the NE list.
			 */
			else if (wp.getLatitude() > startingPoint.getLatitude() && wp.getLongitude() > startingPoint.getLongitude())
			{
				neList.add(wp);
			}
			/*
			 * If this latitude is greater than the starting point (lower) and
			 * the longitude is greater than the starting point (to the left),
			 * put it in the SW list.
			 * 
			 * Note, we compare wp as greater than to the starting point,
			 * because the number is greater than another if it's closer to
			 * zero.
			 */
			else if (wp.getLatitude() < startingPoint.getLatitude() && wp.getLongitude() < startingPoint.getLongitude())
			{
				swList.add(wp);
			}
			/*
			 * If this latitude is greater than the starting point (lower) and
			 * the longitude is less than the starting point (to the right), put
			 * it in the SE list. Note, we compare wp as greater than to the
			 * starting point, because the number is greater than another if
			 * it's closer to zero.
			 */
			else if (wp.getLatitude() < startingPoint.getLatitude() && wp.getLongitude() > startingPoint.getLongitude())
			{
				seList.add(wp);
			}
			else
			{
				System.err.println("Should have found a spot for this waypoints!");
				assert (false);
			}
		}
	}

	public List<Waypoint> getSortedWaypoints()
	{
		return optimizedWaypoints;
	}
}
